package dateStructure;
import java.util.Scanner;

public class list {
    public static class Node{///Java中用内部类
        int date;
        Node next;
    }
    private static Node initList(Node L){
        L=new Node();
        L.next=null;
        return L;
    }
    private static boolean createList_H(Node L){
        Scanner scanner=new Scanner(System.in);
        System.out.print("请输入元素的个数：");
        int n=scanner.nextInt();
        Node p;
        System.out.print("请依次输入每一个元素：");
        while (n-->0){
            p=new Node();///**每次要建立一个新的节点用于插入 不能在外面建立
            p.date=scanner.nextInt();
            ///头插法只有两步 但是输出的是倒序的！！
            p.next=L.next;
            L.next=p;
        }
        return true;
    }
    private static boolean createList_E(Node L){
        Scanner scanner=new Scanner(System.in);
        Node p,r;
        r=L;///链表中没有新元素的时候 头结点和尾结点是一样的
        System.out.print("请输入元素的个数：");
        int n=scanner.nextInt();
        System.out.print("请依次输入每一个元素：");
        while (n-->0){
            p=new Node();
            p.date=scanner.nextInt();
            ///尾插法有三步 但是输出的是正序的！！
            p.next=null;
            r.next=p;//尾部节点的下一个指针指向为新元素，
            r=p;//然后将新元素插入变成尾部指针
        }
        return true;
    }
    public static int getElem_E(Node L,int i){
        int j=1;
        Node p=L.next;
        while (p!=null){
            if(i==j)
                return p.date;
            j++;
            p=p.next;
        }
        return -1;
    }
    public static int locateElem(Node L,int x){
        int j=1;///这个是精确查找 从1开始
        Node p=L.next;
        while (p!=null){
            if(p.date==x)
                return j;
            j++;
            p=p.next;
        }
        return -1;
    }

    /**
     *         如果是为了进行插入或者删除那种操作 p就要从L开始而不是L.next开始
     * @param L
     * @param i
     * @param x
     * @return
     */
    private static boolean listInsert(Node L,int i,int x){///有bug
        Node s,p=L;///从头开始
        int j=0;///插入是要找插入位置的前一个位置 所以从0开始计数
        while (p!=null){
            if(j==i-1){
                s=new Node();
                s.date=x;
                s.next=p.next;
                p.next=s;
                return true;
            }
            j++;
            p=p.next;
        }
        return false;
    }
    private static boolean listDelete(Node L,int i){
        int j=0;
        Node p=L;///和双向链表不同 单向链表删除元素必须要走到被删元素的前面才行
        while (p!=null){
            if(j==i-1){
                p.next=p.next.next;
                return true;
            }
            j++;
            p=p.next;
        }
        return false;
    }
    public static void print(Node L){
        Node p;
        p=new Node();
        p=L.next;
        System.out.print("元素分别为：");
        while (p!=null){
            System.out.print(p.date+" ");
            p=p.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        Node myl=null;
        int choose=-1,x,i;
        System.out.print("1:初始化\n2:（头插法）创建\n3:（尾插法）创建\n4:（默认尾插正序）取值\n5:（默认尾插正序）删除\n6:查找\n7:插入\n8:输出\n");
        Scanner scanner=new Scanner(System.in);
        while (scanner.hasNext()){
            choose=scanner.nextInt();
            if(choose==-1)
                break;
            switch (choose)
            {
                case 1:
                    if((myl=initList(myl))!=null){
                        System.out.println("初始化成功！");
                    }
                    else
                        System.out.println("初始化失败！");
                    break;
                case 2:
                    if(createList_H(myl)){
                        System.out.println("头插法创建完成！");
                    }
                    else{
                        System.out.println("头插法创建失败！");
                    }
                    break;
                case 3:
                    if(createList_E(myl)){
                        System.out.println("尾插法创建完成！");
                    }
                    else{
                        System.out.println("尾插法创建失败！");
                    }
                    break;
                case 4:
                    System.out.print("请输入所取值的位置：");
                    i=scanner.nextInt();
                    if(getElem_E(myl,i)!=-1)
                        System.out.println("所取的值为："+getElem_E(myl,i));
                    else
                        System.out.println("没有这个数！");
                    break;
                case 5:
                    System.out.println("请输入要删除元素的位置：");
                    i=scanner.nextInt();
                    if(listDelete(myl,i)){
                        System.out.println("成功删除！");
                    }
                    else{
                        System.out.println("删除失败！");
                    }
                    break;
                case 6:
                    System.out.println("请输入要查找的数字");
                    x=scanner.nextInt();
                    if(locateElem(myl,x)!=-1){
                        System.out.println("查找的数位置为："+locateElem(myl,x));
                    }
                    else{
                        System.out.println("查找失败！");
                    }
                    break;
                case 7:
                    System.out.print("请输入要插入的位置和数字：");
                    i=scanner.nextInt();
                    x=scanner.nextInt();
                    if(listInsert(myl,i,x)){
                        System.out.println("插入成功！");
                    }
                    else{
                        System.out.println("插入失败！");
                    }
                    break;
                case 8:
                    print(myl);
            }
        }
    }
}

